package com.neusoft.tree.huffman;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Objects;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc 霍夫曼树
 * @date 2025-03-25
 */
public class HuffmanTree {

    /**
     * 创建霍夫曼树
     *
     * @param arr 数组
     * @return 霍夫曼树的根节点
     */
    public static HuffmanNode createHuffmanTree(int[] arr) {
        List<HuffmanNode> nodeList = new ArrayList<>();
        for (int arrValue : arr) {
            // 1、将数组的每个元素都转换成Node节点
            nodeList.add(new HuffmanNode(arrValue));
        }

        // 处理到最后只剩一个根节点
        while (nodeList.size() > 1) {
            // 2、Node节点从小到大排序
            Collections.sort(nodeList);

            // 3、取出根节点权值最小的二叉树的2个Node节点
            HuffmanNode subLeftNode = nodeList.get(0);
            HuffmanNode subRightNode = nodeList.get(1);

            // 4、构建一颗新的二叉树
            HuffmanNode parentNode = new HuffmanNode(subLeftNode.getWeight() + subRightNode.getWeight(), subLeftNode, subRightNode);

            // 5、从集合中删除处理过的Node节点
            nodeList.remove(subLeftNode);
            nodeList.remove(subRightNode);

            // 6、将新创建的parentNode加入到Node集合
            nodeList.add(parentNode);
        }

        return nodeList.get(0);
    }

    /**
     * 前序遍历霍夫曼树
     *
     * @param rootNode 根节点
     */
    public static void preOrder(HuffmanNode rootNode) {
        if (Objects.isNull(rootNode)) {
            System.out.println("空树不能遍历!");
            return;
        }

        rootNode.preOrder();
    }
}
